package com.example.design.leetcode.dfs;

//剑指 Offer 27. 二叉树的镜像
//    请完成一个函数，输入一个二叉树，该函数输出它的镜像。
//
//    例如输入：
//
//      4
//     /  \
//     2   7
//    / \  / \
//    1  3 6  9

//    镜像输出：
//      4
//     /  \
//     7   2
//    / \  / \
//    9  6 3 1
//
//    示例 1：
//    输入：root = [4,2,7,1,3,6,9]
//    输出：[4,7,2,9,6,3,1]
//
//    限制：
//    0 <= 节点个数 <= 1000
//    注意：本题与主站 226 题相同：https://leetcode-cn.com/problems/invert-binary-tree/

// 标签：dfs
public class Practice34 {
    public static TreeNode mirrorTree(TreeNode root) {
        // 递归的出口
        if (root == null) {
            return root;
        }

        // 递归表达式
        TreeNode treeNode = new TreeNode(root.val);
        treeNode.left = mirrorTree(root.right);
        treeNode.right = mirrorTree(root.left);
        return treeNode;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        TreeNode left = new TreeNode(2);
        TreeNode right = new TreeNode(7);
        root.left = left;
        root.right = right;

        TreeNode left1 = new TreeNode(1);
        TreeNode right1 = new TreeNode(3);
        left.left = left1;
        left.right = right1;

        TreeNode left2 = new TreeNode(6);
        TreeNode right2 = new TreeNode(9);
        right.left = left2;
        right.right = right2;


        TreeNode treeNode = mirrorTree(root);
        System.out.println(treeNode);
    }


}
